package leetcode.code1268;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {

	public List<List<String>> suggestedProducts(String[] products, String searchWord) {
		Node root = new Node();
		for (int i = 0; i < products.length; i++) {
			String p = products[i];
			Node node = root;
			for (char c : p.toCharArray()) {
				node = node.computeIfAbsent(c, k -> new Node());
				if (node.queue.isEmpty() || node.queue.size() < 3) {
					node.queue.add(p);
				} else if (node.queue.peek().compareTo(p) > 0) {
					node.queue.poll();
					node.queue.add(p);
				}
			}
		}
		List<List<String>> ans = new ArrayList<>();
		for (char s : searchWord.toCharArray()) {
			if (root == null || !root.containsKey(s)) {
				ans.add(new ArrayList<>());
				root = null;
			} else {
				root = root.get(s);
				PriorityQueue<String> queue = root.queue;
				List<String> add = new ArrayList<>();
				while (!queue.isEmpty()) {
					add.add(queue.poll());
				}
				Collections.reverse(add);
				ans.add(add);
			}
		}
		return ans;
	}

	class Node extends HashMap<Character, Node> {
		PriorityQueue<String> queue = new PriorityQueue<>((a, b) -> b.compareTo(a));
	}

}
